package sort;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/6 12:15
 */
public class BubbleSort {
    public static void main(String[] args) {

    }
    public static void swap(long[] array, int i, int j) {
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    /**
     * 冒泡排序：
     *
     * 时间复杂度：
     * 最好情况：O(n) 当 数组已经有序
     * 平均情况：O(n^2)
     * 最坏情况：O(n^2)  当 数组是逆序的
     *
     * 空间复杂度：
     * 最好/平均/最坏：O(1)
     *
     * 稳定性：具备稳定性
     * @param array
     */
    public static void bubbleSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {    // 需要 n - 1 次冒泡过程
            // 无序区间 [0, array.length - i)
            // 遍历整个无序区间，但是确保相邻的元素两两比较，所以
            // 要遍历的下标范围 [0, array.length - i - 1)

            // 每次冒泡过程时，假设无序区间是有序的
            boolean sorted = true;

            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 这里不加等号，加等号就失去稳定性
                    swap(array, j, j + 1);

                    sorted = false;     // 存在 前面的元素 > 后边的元素，说明假设无序区间有序的假设不成立

                    // 冒泡的过程中，一旦发生了交换，说明
                    // 存在：相邻的两个元素之间，前面的元素 > 后边的元素
                    // 反过来说：单次冒泡给过程，如果一次交换都没有发生过
                    // 说明不存在：相邻的两个元素之间，前面的元素 > 后边的元素
                    // 任意相邻的两个元素之间，前面的元素 <= 后边的元素
                    // 冒泡过程只在无序区间进行
                    // 无序区间的任意相邻的两个元素满足：前面的元素 <= 后边的元素
                    // 我们认为的无序区间是有序的
                    // 所以，整个数组已经全部是有序的了
                }
            }

            // 冒泡过程完成之后，如果 sorted == true，说明一次交换没发生过
            if (sorted) {
                return;
            }
        }
    }
    // [from, to)
    public static void bubbleSort递归版本(long[] array, int from, int to) {
        int size = to - from;
        if (size <= 1) {
            return;
        }

        for (int i = from; i < to - 1; i++) {
            if (array[i] > array[i + 1]) {
                swap(array, i, i + 1);
            }
        }

        // [from, to)
        // [from, to - 1) 无序
        // [to - 1, to)   有序
        // 再用相同的方式处理剩余的问题
        bubbleSort递归版本(array, from, to - 1);
    }
}